﻿\newpage
\section{Результаты экспериментов}
\label{section:results}

Программа, реализующая описанный алгоритм и использующая указанные оптимизации, запускалась на большом количестве различных входных данных. Тестирование проводилось на персональном компьютере с процессором Intel Core 2 Duo 2.33GHz и 2 Гб оперативной памяти. Избранные результаты приведены в Таблице \ref{table:exp}.

Автоматы, распознающие приближения исследуемых языков, подчиняются следующим закономерностям:

\begin{itemize}
\item Во всех построенных автоматах была ровно одна нетривиальная компонента сильной связности. Именно поэтому интерес представляет модификация алгоритма Тарьяна, использующая меньше памяти в этом случае (см. раздел \ref{section:grate}).
\item НОД длин циклов компоненты сильной связности почти во всех автоматах равен 1. В этом случае мы можем не добавлять петлю к каждой вершине в алгоритме вычисления верхней оценки индекса роста. Этот результат важен, поскольку алгоритм в этом случае быстрее находит ответ.
\item Размер компоненты сильной связности увеличивается с ростом экспоненты. Это означает, что для маленьких экспонент выделение компоненты сильной связности и хранение списка рёбер компоненты вместо всего автомата даёт существенный выигрыш в производительности и позволяет получать оценки индексов роста для очень больших автоматов (до 100 миллионов вершин), компонента сильной связности которых мала.
\item Размер очереди играет критическую роль при исследовании языков над большими алфавитами в случае маленьких экспонент. В этом случае распознающий автомат получается сравнительно небольшой, однако для его построения требуется проверить много длинных потенциальных корней. Также размер очереди критичен для исследования $7/5+$-свободного языка над алфавитом из 4 символов. Во всех остальных случаях алгоритм использовал наибольшее количество памяти при вычислении верхней оценки индекса роста, так как на этом этапе нужно для каждой вершины компоненты сильной связности хранить пару счётчиков.
\item Дольше всего алгоритм работает для языков, избегающих малую экспоненту. В этом случае время в основном тратится на построение антисловаря (для больших алфавитов), или на вычисление индекса роста (в случае небольших алфавитов очень велико количество итераций). Эти два фактора сочетаются при исследовании $7/5+$-свободного языка над алфавитом из 4 символов.
\item Представляет интерес поведение индекса роста языка, избегающего экспоненту $\beta$, как функции от $\beta$ (при фиксированном размере алфавита). Из проведённых экспериментов можно сделать предположение о том, что функция $\alpha(\beta)$ для алфавита размера $n \ge 3$ имеет скачки, большие единицы, в точках $\frac{n-1}{n-2}, \frac{n-2}{n-3}, \ldots 2$.
\end{itemize}

\input tables/exp

\newpage
Также были проведены исследования языков над бинарным алфавитом, избегающих шаблоны $(XXY)^2$ и $(XYX)^2$. Верхние оценки индексов роста этих языков оказались близки друг к другу и достаточно велики (см. Таблицу \ref{table:xxy}). Достаточно интересные результаты получаются при рассмотрении избегаемости каждого из этих шаблонов вместе с шаблоном $X^3$. Правило построения антисловаря в обоих случаях практически не изменяется (более того, в обоих случаях шаблон $X^3$ добавляет в антисловарь лишь два слова). Можно также показать, что для этих языков применим описанный в работе способ вычисления нижней оценки индекса роста. Оказывается, пара шаблонов $(XYX)^2$ и $X^3$ неизбежна над бинарным алфавитом (см. примечание \ref{subsection:xyx_ad}), а пара шаблонов $(XXY)^2$ и $X^3$~--- избегаема, хотя индекс роста для шаблона $(XXY)^2$ меньше, чем для шаблона $(XYX)^2$. 

\input tables/xxy
